package string;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class DoublePointer {
    /**
     * 反转字符串
     */
    public void reverseString(char[] s) {
        int i = 0;int j = s.length - 1;
        while(i<j){
            char temp = s[i];
            s[i++] = s[j];
            s[j--] = temp;
        }

    }

    /**
     * 数组拆分I
     */
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if(i%2 == 0){
                sum+=nums[i];
            }

        }
        return sum;
    }

    /**
     * 两数之和II
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i])+1, i+1};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * 移除元素
     */
    public int removeElement(int[] nums, int val) {
        if(nums.length == 0){
            return 0;
        }
        int slowp = 0;
        int fastp = nums.length-1;
        while(slowp < fastp) {
            while (nums[slowp] == val) {
                if(slowp == fastp) {
                    fastp--;
                    break;
                }
                nums[slowp] = nums[fastp];
                fastp--;
            }
            slowp++;
        }
        if(fastp < 0){
            return 0;
        }
        else if(nums[fastp] ==  val) {
            fastp--;
        }
        return fastp+1;
    }

    /**
     * 最大连续1的个数
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int slowp=0;
        int max=0;boolean addable = true;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1 && addable){
                slowp = i;
                addable = false;
            }
            else if(nums[i] == 0 && !addable){
                if(max<i - slowp){
                    max = i - slowp;
                }
                addable = true;
            }
            if(i == nums.length - 1 && !addable){
                max = max<i - slowp + 1?i - slowp + 1:max;
            }
        }
        return max;
    }

    /**
     * 长度最小的子数组
     */
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }


}
